package commonusealgorithm;

import java.util.*;

/**
 * @Author PoX21s
 * @Date: 2021/11/1 19:33
 * @Version 1.0
 */

public class Greedy {
    public static void main(String[] args) {
        HashMap<String, HashSet<String>> broadCasts = new HashMap<>();
        // 创建5个电台，并添加所覆盖的地区
        HashSet<String> k1 = new HashSet<>();
        HashSet<String> k2 = new HashSet<>();
        HashSet<String> k3 = new HashSet<>();
        HashSet<String> k4 = new HashSet<>();
        HashSet<String> k5 = new HashSet<>();

        k5.add("北京");
        k5.add("上海");
        k5.add("天津");

        k2.add("广州");
        k2.add("北京");
        k2.add("深圳");

        k3.add("成都");
        k3.add("上海");
        k3.add("杭州");

        k4.add("上海");
        k4.add("天津");

        k1.add("杭州");
        k1.add("大连");

        broadCasts.put("k1",k1);
        broadCasts.put("k2",k2);
        broadCasts.put("k3",k3);
        broadCasts.put("k4",k4);
        broadCasts.put("k5",k5);
        // 创建一个集合来保存所有地区
        HashSet<String> allAreas = new HashSet<>();

        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("深圳");
        allAreas.add("杭州");
        allAreas.add("成都");
        allAreas.add("大连");
        allAreas.add("广州");
        allAreas.add("天津");
        // 创建一个临时变量来保存电台和所有地区集合的并集
        HashSet<String> tempArea = new HashSet<>();
        // 创建一个集合来保存最后的电台选择
        ArrayList<String> list = new ArrayList<>();
        // 下面是找到第一个覆盖最多地区的电台，并将它加入到最后的选择中
        String maxKey = "k1";

        for (String key : broadCasts.keySet()){
            if (broadCasts.get(maxKey).size() < broadCasts.get(key).size()){
                maxKey = key;
            }
        }
        // 如果所有地区的集合不为空，则一直进行加入电台的操作，直到没有地区没有被覆盖
        while (allAreas.size() != 0){
            for (String key : broadCasts.keySet()){
                tempArea.clear();
                HashSet<String> area = broadCasts.get(key);
                tempArea.addAll(area);
                // 遍历所有电台，一次和地区集合求交集，最大的加入
                tempArea.retainAll(allAreas);
                if (tempArea.size() > 0 &&
                        (maxKey == null || tempArea.size() > broadCasts.get(maxKey).size())) {
                    maxKey = key;
                }
                }

            if (maxKey != null) {
                list.add(maxKey);
                allAreas.removeAll(broadCasts.get(maxKey));
            }
            maxKey = null;
        }
        System.out.println(list);
        }
    }

